1005D - Polycarp and Div 3 - CodeForces Solution


dp greedy number theory *1500

Please click on ads to support us..

Python Code:

n = input()
a = [int(i) for i in n]
tmp = 0
cnt = 0
ans = 0
for i in a:
    t = i % 3
    tmp = (tmp + t) % 3
    cnt += 1
    if t == 0 or tmp == 0 or cnt == 3:
        ans += 1
        cnt = 0
        tmp = 0

print(ans)

C++ Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+100;
const ll M=998244353;
ll dp[N][3];//第i位的余数为0,1,2; 
int main() {
	string s;
	cin>>s;
	ll ans=0,st=0;

	dp[0][0]=dp[0][1]=dp[0][2]=0;
	for(int i=0;i<s.size();i++)
	{
		ll zhi=(s[i]-'0')%3;
		if(zhi==0)
		{
			dp[i][2]=dp[i][1]=dp[i][0]=0;
			ans++;
		}
		else if(zhi==1)
		{
			if(dp[i-1][2])
			{
				dp[i][2]=dp[i][1]=dp[i][0]=0;
				ans++;
			}
			else
			{
				if(dp[i-1][1])dp[i][2]=1;
				else dp[i][2]=0;
				dp[i][1]=1;
			}
		}
		else if(zhi==2)
		{
			if(dp[i-1][1])
			{
				dp[i][2]=0;dp[i][1]=0;dp[i][0]=0;
				ans++;
			}
			else
			{	
				if(dp[i-1][2])dp[i][1]=1;
				else dp[i][1]=dp[i-1][1];dp[i][2]=1;
				
			}
		}
	}
	cout<<ans<<endl;
    return 0;
}
//111112122222221212


Comments

Submit
0 Comments
More Questions

1143B - Nirvana
1285A - Mezo Playing Zoma
919B - Perfect Number
894A - QAQ
1551A - Polycarp and Coins
313A - Ilya and Bank Account
1469A - Regular Bracket Sequence
919C - Seat Arrangements
1634A - Reverse and Concatenate
1619C - Wrong Addition
1437A - Marketing Scheme
1473B - String LCM
1374A - Required Remainder
1265E - Beautiful Mirrors
1296A - Array with Odd Sum
1385A - Three Pairwise Maximums
911A - Nearest Minimums
102B - Sum of Digits
707A - Brain's Photos
1331B - Limericks
305B - Continued Fractions
1165B - Polycarp Training
1646C - Factorials and Powers of Two
596A - Wilbur and Swimming Pool
1462B - Last Year's Substring
1608B - Build the Permutation
1505A - Is it rated - 2
169A - Chores
765A - Neverending competitions
1303A - Erasing Zeroes